/*
 * 1013. Implement strStr()
 * 对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。
 * https://www.lintcode.com/problem/implement-strstr/description
 * 
 * 样例
 * 如果 source = "source" 和 target = "target"，返回 -1。
 * 如果 source = "abcdabcdefg" 和 target = "bcd"，返回 1。
 * 
 * 挑战
 * O(n2)的算法是可以接受的。如果你能用O(n)的算法做出来那更加好。（提示：KMP）
 * 
 * 2018.06.02 @jeyming
 */

public class L0013_Implement_Strstr {
	/*
	 * @param source: source string to be scanned.
	 * @param target: target string containing the sequence of characters to match
	 * @return: a index to the first occurrence of target in source, or -1  if target is not part of source.
	 */
	public static int strStr(String source, String target) {
		// write your code here
		int id = -1;
		if(source == null)
			return -1;
		if(target == null)
			return -1;
		if(source.length() == 0 && target.length() == 0)
			return 0;
		if(source.length() != 0 && target.length() == 0)
			return 0;

		for(int i = 0; i < source.length(); ++i ) {
			if(source.charAt(i) == target.charAt(0)) {
				for(int j = 0,z = i; j < target.length() && z < source.length(); ++j , ++z) {
					if(source.charAt(z) != target.charAt(j)) {
						break;
					}
					if(j == target.length() - 1) {
						return i;
					}
				}
			}
		}
		return id;
	}

	/**
	 * @param source:
	 * @param target:
	 * @return: return the index
	 */
	public int strStr2(String source, String target) {
		// Write your code here
		return source.indexOf(target);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(strStr("source","target"));
		System.out.println(strStr("abcdabcdefg","bcd"));
	}

}
